{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Dot Product of Two Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDotProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个子序列的最大点积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个数组&nbsp;<code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <code>nums1</code> 和 <code>nums2</code> 中两个长度相同的 <strong>非空</strong> 子序列的最大点积。</p>\n",
    "\n",
    "<p>数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，<code>[2,3,5]</code>&nbsp;是&nbsp;<code>[1,2,3,4,5]</code>&nbsp;的一个子序列而&nbsp;<code>[1,5,3]</code>&nbsp;不是。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,1,-2,5], nums2 = [3,0,-6]\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。\n",
    "它们的点积为 (2*3 + (-2)*(-6)) = 18 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [3,-2], nums2 = [2,-6,7]\n",
    "<strong>输出：</strong>21\n",
    "<strong>解释：</strong>从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。\n",
    "它们的点积为 (3*7) = 21 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [-1,-1], nums2 = [1,1]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。\n",
    "它们的点积为 -1 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 500</code></li>\n",
    "\t<li><code>-1000 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>点积：</strong></p>\n",
    "\n",
    "<pre>\n",
    "定义 <code><strong>a</strong>&nbsp;= [<em>a</em><sub>1</sub>,&nbsp;<em>a</em><sub>2</sub>,…,&nbsp;<em>a</em><sub><em>n</em></sub>]</code> 和<strong> <code>b</code></strong><code>&nbsp;= [<em>b</em><sub>1</sub>,&nbsp;<em>b</em><sub>2</sub>,…,&nbsp;<em>b</em><sub><em>n</em></sub>]</code> 的点积为：\n",
    "\n",
    "<img alt=\"\\mathbf{a}\\cdot \\mathbf{b} = \\sum_{i=1}^n a_ib_i = a_1b_1 + a_2b_2 + \\cdots + a_nb_n \" class=\"tex\" src=\"https://pic.leetcode-cn.com/1666164309-PBJMQp-image.png\" />\n",
    "\n",
    "这里的 <strong>Σ</strong> 指示总和符号。\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-dot-product-of-two-subsequences](https://leetcode.cn/problems/max-dot-product-of-two-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-dot-product-of-two-subsequences](https://leetcode.cn/problems/max-dot-product-of-two-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,-2,5]\\n[3,0,-6]', '[3,-2]\\n[2,-6,7]', '[-1,-1]\\n[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if max(nums1) < 0 and min(nums2) > 0:\n",
    "            return max(nums1) * min(nums2)\n",
    "        if min(nums1) > 0 and max(nums2) < 0:\n",
    "            return min(nums1) * max(nums2)\n",
    "        \n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            nextDp = [0] * (n + 1)\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                use = nums1[i] * nums2[j] + dp[j + 1]\n",
    "                nextDp[j] = max(use, dp[j], nextDp[j + 1])\n",
    "            dp = nextDp\n",
    "        return dp[0]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        M = len(nums1)\n",
    "        N = len(nums2)\n",
    "        dp = [0] * N\n",
    "        dp2 = [0] * N\n",
    "        dp[0] = nums1[0] * nums2[0]\n",
    "        for i in range(1, N):\n",
    "            n1 = nums1[0]\n",
    "            dp[i] = max(n1 * nums2[i], dp[i-1])\n",
    "        for i in range(1, M):\n",
    "            dp2, dp = dp, dp2\n",
    "            n1 = nums1[i]\n",
    "            dp[0] = max(n1 * nums2[0], dp2[0])\n",
    "            for j in range(1, N):\n",
    "                m = n1 * nums2[j]\n",
    "                dp[j] = max(m, dp2[j-1] + m, dp[j-1], dp2[j])\n",
    "        return dp[N-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        # 使用记忆化搜索实现\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     t = nums1[i] * nums2[j]\n",
    "        #     return max(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1), dfs(i - 1, j - 1) + t)\n",
    "        # ans = dfs(m - 1, n - 1)\n",
    "        # if ans != 0:\n",
    "        #     return ans\n",
    "        # else:\n",
    "        #     if nums1[0] < 0:\n",
    "        #         return max(nums1) * min(nums2)\n",
    "        #     else:\n",
    "        #         return min(nums1) * max(nums2)\n",
    "\n",
    "        # 使用dp数组实现\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # for i, x in enumerate(nums1):\n",
    "        #     for j, y in enumerate(nums2):\n",
    "        #         dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j], dp[i][j] + x * y)\n",
    "        # ans = dp[m][n]\n",
    "        # if ans != 0:\n",
    "        #     return ans\n",
    "        # else:\n",
    "        #     if nums1[0] < 0:\n",
    "        #         return max(nums1) * min(nums2)\n",
    "        #     else:\n",
    "        #         return min(nums1) * max(nums2)\n",
    "\n",
    "        # 优化数组\n",
    "        # dp = [[0] * (n + 1) for _ in range(2)]\n",
    "        # for i, x in enumerate(nums1):\n",
    "        #     for j, y in enumerate(nums2):\n",
    "        #         dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j], dp[i % 2][j], dp[i % 2][j] + x * y)\n",
    "        # ans = dp[m % 2][n]\n",
    "        # if ans != 0:\n",
    "        #     return ans\n",
    "        # else:\n",
    "        #     if nums1[0] < 0:\n",
    "        #         return max(nums1) * min(nums2)\n",
    "        #     else:\n",
    "        #         return min(nums1) * max(nums2)\n",
    "\n",
    "         # 使用一维数组实现\n",
    "        dp = [0] * (n + 1)\n",
    "        for x in nums1:\n",
    "            pre = dp[0]\n",
    "            for j, y in enumerate(nums2):\n",
    "                tmp = dp[j + 1]\n",
    "                dp[j + 1] = max(dp[j + 1], dp[j], pre, pre + x * y)\n",
    "                pre = tmp\n",
    "        ans = dp[n]\n",
    "        if ans != 0:\n",
    "            return ans\n",
    "        else:\n",
    "            if nums1[0] < 0:\n",
    "                return max(nums1) * min(nums2)\n",
    "            else:\n",
    "                return min(nums1) * max(nums2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "\n",
    "        for i, num2 in enumerate(nums2):\n",
    "            for j, num1 in enumerate(nums1):\n",
    "                temp = num1 * num2\n",
    "                dp[i][j] = temp\n",
    "                if i > 0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j])\n",
    "                if j > 0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j-1])\n",
    "                if i > 0 and j > 0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + temp)   # dp[i - 1][j - 1] 已经被包含在 dp[i][j-1] / dp[i-1][j] 中, 因此不用再考虑\n",
    "                    # dp[i][j] = max(temp, dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        legth1 = len(nums1)\n",
    "        legth2 = len(nums2)\n",
    "        dp = [[0 for i in range(legth2)] for j in range(legth1)]\n",
    "        dp[-1][-1] = nums1[-1] * nums2[-1]\n",
    "        for i in range(max(legth2, legth1) - 2, -1, -1):\n",
    "            if i < legth1 - 1:\n",
    "                dp[i][-1] = max(dp[i + 1][-1], nums1[i] * nums2[-1])\n",
    "            if i < legth2 - 1:\n",
    "                dp[-1][i] = max(dp[-1][i + 1], nums1[-1] * nums2[i])\n",
    "        for i in range(legth1 - 2, -1, -1):\n",
    "            for j in range(legth2 - 2, -1, -1):\n",
    "                dp[i][j] = max(dp[i + 1][j + 1] + nums1[i] * nums2[j], dp[i + 1][j], dp[i][j + 1],nums1[i]*nums2[j])\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        m, n = len(nums1), len(nums2)\n",
    "\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0] = nums1[0]*nums2[0]\n",
    "        for j in range(1,n):\n",
    "            dp[0][j] = max(nums1[0]*nums2[j], dp[0][j-1])\n",
    "        for i in range(1,m):\n",
    "            dp[i][0] = max(nums1[i]*nums2[0], dp[i-1][0])\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = max(\n",
    "                    dp[i-1][j-1]+nums1[i]*nums2[j], nums1[i]*nums2[j], # 选(i,j)\n",
    "                    dp[i-1][j], dp[i][j-1], dp[i-1][j-1]\n",
    "                )\n",
    "\n",
    "        print(dp)\n",
    "\n",
    "        return dp[m-1][n-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \n",
    "                        n = len(nums1)\n",
    "                        m = len(nums2)\n",
    "                        kkk = min(n,m) + 1\n",
    "                        f = [[-inf for i in range(m+1)] for j in range(n+1)]\n",
    "                        # for j in range(m+1):\n",
    "                        #     for k in range(kkk):\n",
    "                        #         f[0][j][k] = 0\n",
    "                        # for i in range(n+1):\n",
    "                        #     for k in range(kkk):\n",
    "                        #         f[i][0][k] = 0\n",
    "                        f[0][0] = 0\n",
    "                        \n",
    "                        for i in range(1,n+1):\n",
    "                            for j in range(1,m+1):\n",
    "                                f[i][j] = max(f[i][j],f[i-1][j],f[i][j-1],f[i-1][j-1] + nums1[i-1] * nums2[j-1],nums1[i-1] * nums2[j-1])\n",
    "                                    \n",
    "                        return f[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        max_single = -10 ** 9\n",
    "        for i in range(n1):\n",
    "            for j in range(n2):\n",
    "                max_single = max(max_single, nums1[i] * nums2[j])\n",
    "        if max_single < 0:\n",
    "            return max_single\n",
    "        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        pqs = [[] for _ in range(n2 + 1)]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                heapq.heappush(pqs[j], -dp[i - 1][j - 1] - nums1[i - 1] * nums2[j - 1])\n",
    "                dp[i][j] = max(dp[i][j - 1], -pqs[j][0])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n,m = len(nums1),len(nums2)\n",
    "        if not n or not m:\n",
    "            return 0\n",
    "        dp = [[float('-inf') for _ in range(m+1)] for _ in range(n+1)]\n",
    "        for i,x in enumerate(nums1):\n",
    "            for j,y in enumerate(nums2):\n",
    "                xy = x*y\n",
    "                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],dp[i][j]+xy,xy)\n",
    "        print(dp)\n",
    "        return dp[n][m]\n",
    "        # n,m = len(nums1),len(nums2)\n",
    "        # if not n or not m:\n",
    "        #     return 0\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0 or j<0:\n",
    "        #         return float('-inf')\n",
    "        #     x = nums1[i]*nums2[j]\n",
    "        #     return max(dfs(i-1,j-1)+x,x,dfs(i-1,j),dfs(i,j-1))\n",
    "        # return dfs(n-1,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        prod = [[i*j for i in nums1] for j in nums2]\n",
    "        mx_prod = max([max(i) for i in prod])\n",
    "        if mx_prod < 0:\n",
    "            return mx_prod\n",
    "        m, n = len(nums2), len(nums1)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp1 = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp1[i-1][j-1] + max(0, prod[i-1][j-1])\n",
    "                dp1[i][j] = max(dp1[i-1][j], dp1[i][j-1], dp[i][j])\n",
    "        return dp1[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        dp = [[[0]*2 for _ in range(n2+1)] for _ in range(n1+1)]\n",
    "        for now1 in range(n1+1):\n",
    "            dp[now1][n2][0] = -inf\n",
    "        for now2 in range(n2+1):\n",
    "            dp[n1][now2][0] = -inf\n",
    "        for now1 in range(n1-1, -1, -1):\n",
    "            for now2 in range(n2-1, -1, -1):\n",
    "                for choose in range(1, -1, -1):\n",
    "                    dp[now1][now2][choose] = max(\n",
    "                        dp[now1+1][now2][choose],\n",
    "                        dp[now1][now2+1][choose],\n",
    "                        nums1[now1]*nums2[now2] + dp[now1+1][now2+1][True],\n",
    "                    )\n",
    "        return dp[0][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def __init(self):\n",
    "        self.m = None\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a = np.array(nums1)\n",
    "        b = np.array(nums2)\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        a = np.expand_dims(a, -1)\n",
    "        b = np.expand_dims(b, 0)\n",
    "        prod = np.matmul(a, b).astype(int)\n",
    "\n",
    "        res = np.zeros_like(prod, dtype=int)\n",
    "        res[0, 0] = prod[0, 0]\n",
    "        for i in range(1, m):\n",
    "            res[i, 0] = max(res[i-1, 0], prod[i, 0])\n",
    "        for j in range(1, n):\n",
    "            res[0, j] = max(res[0, j-1], prod[0, j])\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                notake = max(res[i-1, j], res[i, j-1])\n",
    "                take = max(0, res[i-1, j-1]) + prod[i, j]\n",
    "                res[i, j] = max(take, notake)\n",
    "        return int(res[i, j])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int, k: int):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0 if k > 0 else -inf\n",
    "            \n",
    "        #     return max(dfs(i-1, j, k), dfs(i, j-1, k), dfs(i-1, j-1, k+1) + nums1[i] * nums2[j])\n",
    "        \n",
    "        # return dfs(n1-1, n2-1, 0)\n",
    "\n",
    "        f = [[[-inf, 0] for j in range(n2 + 1)] for _ in range(n1 + 1)]\n",
    "        for i in range(n1+1):\n",
    "            f[i][0][1] = -inf\n",
    "        for j in range(n2+1):\n",
    "            f[0][j][1] = -inf\n",
    "        for i, x in enumerate(nums1):\n",
    "            for j, y in enumerate(nums2):\n",
    "                f[i+1][j+1][0] = max(f[i][j+1][0], f[i+1][j][0])\n",
    "                f[i+1][j+1][1] = max(f[i][j+1][1], f[i+1][j][1], x*y, f[i][j][1]+x*y)\n",
    "        # print(f)\n",
    "        return max(f[n1][n2][0], f[n1][n2][1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int, k: int):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0 if k > 0 else -inf\n",
    "            \n",
    "        #     return max(dfs(i-1, j, k), dfs(i, j-1, k), dfs(i-1, j-1, k+1) + nums1[i] * nums2[j])\n",
    "        \n",
    "        # return dfs(n1-1, n2-1, 0)\n",
    "\n",
    "        f = [[[-inf, 0] for j in range(n2 + 1)] for _ in range(n1 + 1)]\n",
    "        for i in range(n1+1):\n",
    "            f[i][0][1] = -inf\n",
    "        for j in range(n2+1):\n",
    "            f[0][j][1] = -inf\n",
    "        for i, x in enumerate(nums1):\n",
    "            for j, y in enumerate(nums2):\n",
    "                f[i+1][j+1][0] = max(f[i][j+1][0], f[i+1][j][0])\n",
    "                f[i+1][j+1][1] = max(f[i][j+1][1], f[i+1][j][1], x*y, f[i][j][1]+x*y)\n",
    "        print(f)\n",
    "        return max(f[n1][n2][0], f[n1][n2][1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        self.mem = {}\n",
    "        min1, max1 = min(nums1), max(nums1)\n",
    "        min2, max2 = min(nums2), max(nums2)\n",
    "\n",
    "        if min1 >= 0 and max2 <= 0:\n",
    "            return min1 * max2\n",
    "        if min2 >= 0 and max1 <= 0:\n",
    "            return min2 * max1 \n",
    "\n",
    "        self.nums1 = nums1\n",
    "        self.nums2 = nums2\n",
    "        \n",
    "        return self.helper(len(self.nums1) - 1, len(self.nums2) - 1)\n",
    "    \n",
    "    def helper(self, i, j):\n",
    "        if i == -1 or j  == -1:\n",
    "            return 0 \n",
    "        \n",
    "        key = (i, j)\n",
    "        if key in self.mem:\n",
    "            return self.mem[key]\n",
    "        \n",
    "        res_helper = self.helper(i - 1, j - 1)\n",
    "        res_helper = max(res_helper, res_helper + self.nums1[i] * self.nums2[j])\n",
    "        res_helper = max(res_helper, self.helper(i - 1, j))\n",
    "        res_helper = max(res_helper, self.helper(i, j - 1))\n",
    "\n",
    "        self.mem[key] = res_helper\n",
    "        return self.mem[key]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return max(nums1[i]*nums2[k] for k in range(j+1))\n",
    "            if j == 0:\n",
    "                return max(nums2[j]*nums1[k] for k in range(i+1))\n",
    "            if nums1[i]*nums2[j] >= 0:\n",
    "                return max(max(dfs(i-1,j-1), 0)+nums1[i]*nums2[j], dfs(i-1,j), dfs(i,j-1))\n",
    "            else:\n",
    "                return max(dfs(i-1,j-1), dfs(i-1,j), dfs(i,j-1))\n",
    "        return dfs(m-1, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        dp = defaultdict(lambda: -inf)\n",
    "        for i1, num1 in enumerate(nums1):\n",
    "            for i2, num2 in enumerate(nums2):\n",
    "                dp[(i1, i2)] = max(dp[(i1-1, i2-1)] + num1 * num2, num1 * num2, dp[(i1-1, i2)], dp[(i1, i2-1)])\n",
    "        \n",
    "        return dp[(n1-1, n2-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dp = collections.defaultdict(int)\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        res = -float('inf')\n",
    "        premx = [-float('inf')] * n2\n",
    "        curmx = [-float('inf')] * n2\n",
    "        for i in range(n1):\n",
    "            premx = curmx[::]\n",
    "            for j in range(n2):\n",
    "                v = nums1[i] * nums2[j]\n",
    "                dp[i,\n",
    "                   j] = v if j - 1 < 0 or premx[j - 1] < 0 else v + premx[j -\n",
    "                                                                          1]\n",
    "                res = max(res, dp[i, j])\n",
    "                curmx[j] = max(curmx[j], dp[i, j])\n",
    "                if j - 1 >= 0:\n",
    "                    curmx[j] = max(curmx[j], curmx[j - 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "\n",
    "        # 需要考虑一个数组全是负数，和一个全是正数情况\n",
    "        if max(nums1) < 0 and min(nums2) > 0:\n",
    "            return max(nums1) * min(nums2)\n",
    "        if max(nums2) < 0 and min(nums1) > 0:\n",
    "            return max(nums2) * min(nums1)\n",
    "\n",
    "        @lru_cache(len(nums1) * len(nums2))\n",
    "        def dfs(i, j):\n",
    "            if i >= len(nums1) or j >= len(nums2):\n",
    "                return 0\n",
    "            # 0,0\n",
    "            op1 = dfs(i + 1, j + 1)\n",
    "            # 1,1\n",
    "            op2 = dfs(i + 1, j + 1) + nums1[i] * nums2[j]\n",
    "            # 1,0\n",
    "            op3 = dfs(i + 1, j)\n",
    "            # 0,1\n",
    "            op4 = dfs(i, j + 1)\n",
    "            return max([op1, op2, op3, op4])\n",
    "\n",
    "        res = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1=len(nums1)\n",
    "        n2=len(nums2)\n",
    "        dic={}\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in dic:\n",
    "                return dic[(i,j)]\n",
    "            if i==n1-1 and j==n2-1:\n",
    "                res = nums1[i]*nums2[j]\n",
    "            elif i==n1-1:\n",
    "                res=max(dfs(i,j+1),nums1[i]*nums2[j])\n",
    "            elif j==n2-1:\n",
    "                res=max(dfs(i+1,j),nums1[i]*nums2[j])\n",
    "            else:\n",
    "                res= max(dfs(i+1,j),dfs(i,j+1),dfs(i+1,j+1),dfs(i+1,j+1)+nums1[i]*nums2[j],nums1[i]*nums2[j])\n",
    "            dic[(i,j)] = res \n",
    "            return res\n",
    "        return dfs(0,0)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        @cache\n",
    "        def getRes(idx1, idx2, flag):\n",
    "            if idx1 == n1 or idx2 == n2:\n",
    "                return 0 if flag else -inf\n",
    "            return max(getRes(idx1+1, idx2, flag), getRes(idx1, idx2+1, flag), getRes(idx1+1, idx2+1, True) + nums1[idx1] * nums2[idx2])\n",
    "        ans = getRes(0, 0, False)\n",
    "        getRes.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        # # 回溯转循环\n",
    "        # f = [[-inf]*(n+1) for _ in range(m+1)]\n",
    "        # for j in range(n):\n",
    "        #     f[0][j+1] = max(f[0][j], nums1[0]*nums2[j])\n",
    "        # print(f)\n",
    "        # for i, x in enumerate(nums1):\n",
    "        #     f[i+1][0] = max(f[i][0], x*nums2[0])\n",
    "        #     for j, y in enumerate(nums2):\n",
    "        #         if x * y >= 0:\n",
    "        #             f[i+1][j+1] = max(max(f[i][j], 0)+x*y, f[i][j+1], f[i+1][j])\n",
    "        #         else:\n",
    "        #             f[i+1][j+1] = max(f[i][j], f[i][j+1], f[i+1][j])\n",
    "        # print(f)\n",
    "        # return f[m][n]\n",
    "\n",
    "        # 回溯\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j == 0:\n",
    "                return nums1[i]*nums2[j]\n",
    "            if i == 0:\n",
    "                return max(dfs(i,j-1), nums1[i]*nums2[j])\n",
    "                # print(max(nums1[i]*nums2[k] for k in range(j+1)))\n",
    "                # return max(nums1[i]*nums2[k] for k in range(j+1))\n",
    "            if j == 0:\n",
    "                return max(dfs(i-1,j), nums1[i]*nums2[j])\n",
    "                # print(max(nums2[j]*nums1[k] for k in range(i+1)))\n",
    "                # return max(nums2[j]*nums1[k] for k in range(i+1))\n",
    "            if nums1[i]*nums2[j] >= 0:\n",
    "                return max(max(dfs(i-1,j-1), 0)+nums1[i]*nums2[j], dfs(i-1,j), dfs(i,j-1))\n",
    "            else:\n",
    "                return max(dfs(i-1,j-1), dfs(i-1,j), dfs(i,j-1))\n",
    "        return dfs(m-1, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n,m = len(nums1),len(nums2)\n",
    "        if not n or not m:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i < 0 or j<0:\n",
    "                return float('-inf')\n",
    "            x = nums1[i]*nums2[j]\n",
    "            return max(dfs(i-1,j-1)+x,x,dfs(i-1,j),dfs(i,j-1))\n",
    "        return dfs(n-1,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        # 使用记忆化搜索实现\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            t = nums1[i] * nums2[j]\n",
    "            return max(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1), dfs(i - 1, j - 1) + t)\n",
    "        ans = dfs(m - 1, n - 1)\n",
    "        if ans != 0:\n",
    "            return ans\n",
    "        else:\n",
    "            if nums1[0] < 0:\n",
    "                return max(nums1) * min(nums2)\n",
    "            else:\n",
    "                return min(nums1) * max(nums2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(nums1) or j == len(nums2):\n",
    "                return -inf\n",
    "            \n",
    "            t = nums1[i] * nums2[j] + dfs(i+1, j+1)\n",
    "            t = max(t, dfs(i+1, j), dfs(i, j+1), nums1[i] * nums2[j])\n",
    "            return t\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @functools.cache\n",
    "        def dp(i,j):\n",
    "            if i == L1 or j == L2:\n",
    "                return 0\n",
    "            \n",
    "            return max(max(nums1[i]*nums2[j], 0) + dp(i+1, j+1),\n",
    "                        dp(i+1, j),\n",
    "                        dp(i,j+1))\n",
    "        \n",
    "\n",
    "        L1, L2 = len(nums1),len(nums2)\n",
    "        res = dp(0, 0)\n",
    "        if res == 0:\n",
    "            return max(n1*n2 for n1 in nums1 for n2 in nums2)\n",
    "        else:\n",
    "            return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        # cache = {}\n",
    "        @lru_cache(len(nums1) * len(nums2))\n",
    "        def recursion(i,j):\n",
    "            # stri = str(i)\n",
    "            # strj = str(j)\n",
    "            # key = stri + '-' + strj\n",
    "            # if key in cache:\n",
    "                # return cache[key]\n",
    "\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            \n",
    "            res1 = recursion(i - 1, j - 1)\n",
    "            res2 = recursion(i - 1, j)\n",
    "            res3 = recursion(i, j - 1)\n",
    "            res4 = recursion(i - 1, j - 1) + nums1[i] * nums2[j]\n",
    "            # cache[key] = max([res1, res2, res3, res4])\n",
    "            # return cache[key]\n",
    "            return max([res1, res2, res3, res4])\n",
    "        \n",
    "        res = recursion(len(nums1) - 1, len(nums2) - 1)\n",
    "        if res != 0:\n",
    "            return res\n",
    "        else:\n",
    "            l1 = nums1[0]\n",
    "            r1 = nums1[0]\n",
    "            l2 = nums2[0]\n",
    "            r2 = nums2[0]\n",
    "            for i in nums1:\n",
    "                if i < l1:\n",
    "                    l1 = i\n",
    "                if i > r1:\n",
    "                    r1 = i\n",
    "            for i in nums2:\n",
    "                if i < l2:\n",
    "                    l2 = i\n",
    "                if i > r2:\n",
    "                    r2 = i\n",
    "            return max([l1 * l2, l1 * r2, r1 * l2, r1 * r2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        视作类01背包问题，数组中每个元素只有选和不选两种状态\n",
    "        两个数组组合就有四种状态\n",
    "        \"\"\"\n",
    "        from functools import lru_cache\n",
    " \n",
    "        @lru_cache(len(nums1) * len(nums2))\n",
    "        def product(i, j):\n",
    "            if i >= len(nums1) or j >= len(nums2):\n",
    "                return 0\n",
    "            # 两个都不选\n",
    "            op1 = product(i + 1, j + 1)\n",
    "            # 两个都选\n",
    "            op2 = product(i + 1, j + 1) + nums1[i] * nums2[j]\n",
    "            # 只选第一个\n",
    "            op3 = product(i + 1, j)\n",
    "            # 只选第二个\n",
    "            op4 = product(i, j + 1)\n",
    "            return max([op1, op2, op3, op4])\n",
    "\n",
    "        ans = product(0, 0)\n",
    "        if ans > 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return max(min(nums1) * max(nums2), max(nums1) * min(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @cache\n",
    "        def f(i, j, flag):\n",
    "            if i<0 or j<0:\n",
    "                return 0 if flag else -inf\n",
    "\n",
    "            return max(f(i-1, j-1, 1)+nums1[i]*nums2[j], f(i-1, j-1, flag), f(i-1, j, flag), f(i, j-1, flag))\n",
    "\n",
    "        return f(len(nums1)-1, len(nums2)-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, f: bool) -> int:\n",
    "            if i == 0:\n",
    "                res = max(nums1[0] * x for x in nums2[ : j + 1])\n",
    "                if f:\n",
    "                    return res\n",
    "                else:\n",
    "                    return res if res > 0 else 0\n",
    "            if j == 0:\n",
    "                res = max(nums2[0] * x for x in nums1[ : i + 1])\n",
    "                if f:\n",
    "                    return res\n",
    "                else:\n",
    "                    return res if res > 0 else 0\n",
    "            if f:\n",
    "                return max(dfs(i - 1, j - 1, False) + nums1[i] * nums2[j], dfs(i - 1, j, True), dfs(i, j - 1, True), dfs(i - 1, j - 1, True))\n",
    "            else:\n",
    "                return max(dfs(i - 1, j - 1, False) + nums1[i] * nums2[j], dfs(i - 1, j, False), dfs(i, j - 1, False), dfs(i - 1, j - 1, False))\n",
    "        return dfs(m - 1, n - 1, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        @cache\n",
    "        def dfs(i,j,flag):\n",
    "            if i<0 or j<0:\n",
    "                return 0 if flag else -inf\n",
    "\n",
    "            return max(dfs(i-1,j-1,True)+nums1[i]*nums2[j],dfs(i-1,j,flag),dfs(i,j-1,flag))\n",
    "        return dfs(m-1,n-1,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        @cache\n",
    "        def fn(i: int, j: int, empty: bool) -> int:\n",
    "            if i >= m or j >= n:\n",
    "                return float(\"-inf\") if empty else 0\n",
    "            return max(\n",
    "                # nums1[i]选，nums2[j]选\n",
    "                nums1[i] * nums2[j] + fn(i + 1, j + 1, False), \n",
    "                # nums1[i]选，nums2[j]不选\n",
    "                fn(i, j + 1, empty), \n",
    "                # nums1[i]不选，nums2[j]选\n",
    "                fn(i + 1, j, empty), \n",
    "                # nums1[i]不选，nums2[j]不选\n",
    "                fn(i + 1, j + 1, empty), \n",
    "            )\n",
    "        return fn(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, flag):\n",
    "            if i >= len(nums1) or j >= len(nums2):\n",
    "                if flag:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return -inf\n",
    "            res = max(nums1[i] * nums2[j] + dfs(i + 1, j + 1, True), dfs(i, j + 1, flag), dfs(i + 1, j, flag))\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0, False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
